package Sort;

/**
 * 排序(4)
 * 冒泡排序
 * 以升序为例：前面的数大于后面的数则交换这两个数的位置
 * 排序次数 数组长度-1
 * 每次遍历都把最大值排到了未排序序列的最后
 * (简单说：第n次排序，都是把第n大的数，排在倒数第n位)
 */
public class BubbleSort extends Template {


//   无注释（简单优化前）
//    int N = a.length;
//        for (int i=0;i<N-1;i++){
//        for (int j=0;j<N-1-i;j++){
//            if (!less(a[j],a[j+1])) {
//                exch(a,j,j+1);
//            }
//        }
//    }


    //    //升序（简单优化前）
//    public static void sort(Comparable[] a) {
//        int N = a.length;//数组长度
//        for (int i=0;i<N-1;i++){
//            for (int j=0;j<N-1-i;j++){
//                if (!less(a[j],a[j+1])) {//a[j]>a[j+1]则交换
//                    exch(a,j,j+1);
//                }
//            }
//            System.out.println("第"+(i+1)+"次遍历结果，把第"+(i+1)+"大的数，排在倒数第"+(i+1)+"位");
//            show(a);
//        }
//    }
//升序（简单优化后）
    public static void sort(Comparable[] a) {
        int N = a.length;//数组长度
        boolean flag = false;//设置标识变量，标识本次遍历中是否有元素交换
        // (flag默认为true，代表为没有交换过)
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 1 - i; j++) {
                if (!less(a[j], a[j + 1])) {//a[j]>a[j+1]则交换
                    exch(a, j, j + 1);
                    flag = true;//交换过元素
                }
            }
            //System.out.println("第" + (i + 1) + "次遍历结果，把第" + (i + 1) + "大的数，排在倒数第" + (i + 1) + "位");
            //show(a);
            if (!flag) {//若本次遍历中没有发生元素交换，则数组已经排序好，退出循环
                break;
            } else {
                flag = false;
            }
        }
    }


//   （简单优化后）无注释
//    public static void sort(Comparable[] a) {
//        int N = a.length;
//        boolean flag=false;
//        for (int i = 0; i < N-1; i++) {
//            for (int j = 0; j < N - 1 - i; j++) {
//                if (!less(a[j], a[j + 1])) {
//                    exch(a, j, j + 1);
//                    flag=true;
//                }
//            }
//            if(!flag){
//                break;
//            }else {
//                flag=false;
//            }
//        }
//    }

    public static void main(String[] args) {

        Comparable[] a = Template.getData(20);
        System.out.println("冒泡排序前");

        show(a);
        sort(a);

        assert isSorted(a);
        System.out.println("冒泡排序后");
        show(a);
    }

}
